package com.zhuang.linkedlist.linked;

import com.zhuang.linkedlist.abstractclass.AbstractList;

public class DoubleLinkedList<E> extends AbstractList<E> {
	// 约定：在说链表查找元素位置时，我还是将index 称之为索引
	private Node first;
	private Node last;

	private static class Node<E> {
		Node<E> pre;
		Node<E> next;
		E element;

		public Node(Node pre, Node next, E element) {
			this.pre = pre;
			this.next = next;
			this.element = element;
		}
	}

	private Node<E> node(int index) {
		Node node = first;
		// 先去判断要查找的index 是靠近头还是靠近尾，如果靠近头，从头开始找，如果靠近尾巴，从尾开始
		if (index > size >> 1) {
			// 靠近尾
			node = last;
			for (int i = size - 1; i > index; i--) {
				node = node.pre;
			}
		} else {
			// 靠近头
			for (int i = 0; i < index; i++) {
				node = node.next;
			}
		}
		return node;
	}

	@Override
	public E get(int index) {
		checkElementIndex(index);
		return node(index).element;
	}

	@Override
	public E set(int index, E element) {
		checkElementIndex(index);
		Node<E> node = node(index);
		E oldElement = node.element;
		node.element = element;
		return oldElement;
	}

	@Override
	public void add(int index, E element) {
		checkPostionIndex(index);
		// 1. 获得指定的index 2.前一个节点的获取， 3 构建新的now -> 完成指向关系 4.改变1,2的指向
		if (index == size) {
			// 1. 添加到末尾 || 2.没有元素的时候
			linkLast(element);
		} else {
			linkBefore(element, node(index));
		}
		size++;

	}

	private void linkLast(E element) {
		// 1.拿到last 节点
		Node<E> node = last;
		// 2.构建node完成他的指向关系
		Node<E> newNode = new Node(node, null, element);
		// 3.将链表的last进行修改
		last = newNode;
		if (node == null)
			first = newNode;
		else {
			// 4.将原来的last节点的next修改成新构建出来的node
			node.next = newNode;
		}
	}

	private void linkBefore(E element, Node node) {
		// node的前驱节点
		Node<E> pre = node.pre;
		// 新的节点
		Node<E> newNode = new Node(pre, node, element);
		// 新节点赋值给node前驱
		node.pre = newNode;
		if (pre == null) {
			// 就是头节点
			first = newNode;
		} else {
			// 前驱节点的后继节点就是新的节点
			pre.next = newNode;
		}
	}

	@Override
	public E remove(int index) {
		// 1.获得删除的元素
		Node<E> node = node(index);
		// 2.获取前驱节点
		Node<E> pre = node.pre;
		// 3.获取后继节点
		Node<E> next = node.next;

		if (pre == null) {
			// 说明node是头节点
			// 后继节点顶上头节点
			first = next;
			// 前驱节点置为空
			next.pre = null;
		} else {
			pre.next = next;
		}

		if (next == null) {
			// 说明node是尾节点
			// pre直接成为last
			last = pre;
		} else {
			next.pre = pre;
		}

		size--;

		return node.element;
	}

	@Override
	public int indexOf(E element) {
		// 查找有没有element元素，如果有返回element元素的索引，如果没有则返回-1
		Node<E> node = first;
		int index = 0;
		if (element == null) {
			for (Node<E> i = node; node != null; node = node.next) {
				if (element == node.element) {
					return index;
				}
				index++;
			}
		} else {
			for (Node<E> i = node; node != null; node = node.next) {
				if (element == node.element) {
					return index;
				}
				index++;
			}
		}
		return -1;
	}

	@Override
	public void clear() {
		size = 0;
		first = null;
		last = null;
	}

	// 判断索引是否合法
	private boolean isElementIndex(int index) {
		// 满足条件
		return index >= 0 && index < size;
	}

	// 检查元素索引
	private void checkElementIndex(int index) {

		if (!isElementIndex(index)) {
			throw new IndexOutOfBoundsException(": Index: " + index + ", Size: " + size);
		}

	}

	// 检查索引位置
	private void checkPostionIndex(int index) {
		if (!isPostionIndex(index)) {
			throw new IndexOutOfBoundsException(": Index: " + index + ", Size: " + size);
		}
	}

	// 检查索引的合法性
	private boolean isPostionIndex(int index) {
		return index >= 0 && index <= size;
	}

	public String toString() {

		if (size == 0) {
			return "[]";
		}
		StringBuilder sb = new StringBuilder().append("[");
		Node<E> node = first;
		for (Node<E> i = node; i != null; i = i.next) {
			sb.append(i.element);
			if (i.next == null) {
				return sb.append("]").toString();
			}
			sb.append(",");
		}
		return sb.toString();
	}

}
